package week01

// 560. 和为K的子数组
// https://leetcode-cn.com/problems/subarray-sum-equals-k/

// 前缀和
// 子段和

func subarraySum(nums []int, k int) int {
	var sums = make([]int, len(nums)+1)
	for i := 1; i <= len(nums); i++ {
		sums[i] = sums[i-1] + nums[i-1]
	}
	// for i
	//      for j  j < i
	// s[i] - k = s[j]
	// map中只放 i 之前 s[j] 的个数
	var counts = make(map[int]int)
	var ans = 0
	for i := 0; i < len(sums); i++ {
		ans += counts[sums[i]-k]
		counts[sums[i]]++
	}

	return ans
}